package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         312,
		Discription: "戳气球",
		Level:       3,
		Labels: map[string]int{
			"动态规划":  1,
			"虚拟头指针": 1,
		},
	})
}

func MaxCoins(nums []int) int {
	n := len(nums)
	//头尾各加一个值为1的元素，方便处理边界
	tempNums := make([]int, n+2)
	for i := 1; i <= n; i++ {
		tempNums[i] = nums[i-1]
	}
	tempNums[0] = 1
	tempNums[n+1] = 1

	//gains[i][j]表示（i,j）内戳爆气球的最大收益
	gains := make([][]int, n+2)
	for i := 0; i < n+2; i++ {
		gains[i] = make([]int, n+2)
		if i+2 <= n+1 {
			//初始化区间内只有一个气球的
			gains[i][i+2] = tempNums[i] * tempNums[i+1] * tempNums[i+2]
		}
	}

	//想成添加气球，结果和戳气球一样的
	for i := n - 1; i >= 0; i-- {
		for j := i + 2; j <= n+1; j++ {
			//最后一个戳爆的气球的位置
			for k := i + 1; k <= j-1; k++ {
				//由于是倒过来放气球，所以最先放进去（最后被戳爆）的气球的收益是tempNums[i]*tempNums[k]*tempNums[j]
				gains[i][j] = max(gains[i][j], tempNums[i]*tempNums[k]*tempNums[j]+gains[i][k]+gains[k][j])
			}
		}
	}

	return gains[0][n+1]
}
